1. Field of the Invention
The present invention relates to a wireless communications protocol. More specifically, the present invention discloses a data discarding acknowledgment protocol that enables a transmitter to correctly determine the number of layer 2 service data units (SDUs) discarded by a receiver.
2. Description of the Prior Art
The surge in public demand for wireless communication devices has placed pressure upon industry to develop increasingly sophisticated communications standards. The 3rd Generation Partnership Project (3GPP™) is an example of such a new communications protocol. Such standards utilize a three-layer approach to communications. Please refer to FIG. 1. FIG. 1 is a block diagram of the three layers in a communications protocol. In a typical wireless environment, a first station 10 is in wireless communications with one or more second stations 20. An application 13 on the first station 10 composes a message 11 and has it delivered to the second station 20 by handing the message 11 to a layer 3 interface 12. The layer 3 interface 12 may generate some layer 3 signaling messages 12a for the purpose of controlling layer 3 operations, such as ciphering key changes used by the layer 3 interfaces 12 and 22 of both the first and the second stations, respectively. The layer 3 interface 12 delivers either the message 11 or the layer 3 signaling message 12a to a layer 2 interface 16 in the form of layer 2 service data units (SDUs) 14. The layer 2 SDUs 14 maybe of any length. The layer 2 interface 16 composes the SDUs 14 into one or more layer 2 protocol data units (PDUs) 18. Each layer 2 PDU 18 is of a fixed length, and is delivered to a layer 1 interface 19. The layer 1 interface 19 is the physical layer, transmitting data to the second station 20. The transmitted data is received by the layer 1 interface 29 of the second station 20 and reconstructed into one or more PDUs 28, which are passed up to the layer 2 interface 26. The layer 2 interface 26 receives the PDUs 28 and builds up one or more layer 2 SDUs 24. The layer 2 SDUs 24 are passed up to the layer 3 interface 22. The layer 3 interface 22 in turn converts the layer 2 SDUs 24 back into either a message 21, which should be identical to the original message 11 that was generated by the application 13 on the first station 10, or a layer 3 signaling message 22a, which should be identical to the original signaling message 12a generated by the layer 3 interface 12 and which is then processed by the layer 3 interface 22. The received message 21 is passed to an application 23 on the second station 20.
Of particular interest is the layer 2 interface, which acts as a buffer between the relatively high-end data transmission and reception requests of the applications and layer 3, and the low-level requirements of the physical transmission and reception process at layer 1. Please refer to FIG. 2. FIG. 2 is a diagram of a transmission/reception process from a layer 2 perspective. The layer 2 interface 32 of a first station 30 receives a string of SDUs 34 from layer 3. The layer 2 SDUs 34 are sequentially ordered from 1 to 5, and are of an unequal length. The layer 2 interface 32 converts the string of SDUs 34 into a string of layer 2 PDUs 36. The layer 2 PDUs 36 are sequentially ordered from 1 to 4, and are all of an equal length. The string of layer 2 PDUs 36 is then sent off to the layer 1 interface for transmission. A reverse process occurs at the second station 40, with the second station 40 layer 2 interface 42 converting a received string of layer 2 PDUs 46 into a received string of layer 2 SDUs 44, which are then passed up to layer 3. There are two delivery modes: in-sequence delivery and out-of-sequence delivery. If the established connection between the first station 30 and the second station 40 is configured to be in the in-sequence delivery mode, the multi-layered protocol insists that the layer 2 interface 42 present the SDUs 44 to layer 3 in order. That is, the layer 2 interface 42 must present the layer 2 SDUs 44 to layer 3 in the sequential order of the SDUs 44, beginning with SDU 1 and ending with SDU 5. The ordering of the SDUs 44 may not be scrambled, nor may a subsequent SDU be delivered to layer 3 until all of the prior SDUs have been delivered. However, if the established connection is configured to be in the out-of-sequence delivery mode, the layer 2 interface 42 can present the layer 2 SDUs 44 to layer 3 out of sequential order.
In line transmissions, such requirements are relatively easy to fulfill. In the noisy environment of wireless transmissions, however, the second station 40 often misses data. Some layer 2 PDUs in the received string of layer 2 PDUs 46 will therefore be missing. Thus, ensuring that the layer 3 SDUs 44 are presented in order, when the system is in the in-sequence delivery mode, can pose a significant challenge. Even in the out-of sequence delivery mode, a layer 2 SDU can not be presented until all of its composing layer 2 PDUs have been correctly received. Please refer to FIG. 3. FIG. 3 is a block diagram of a data PDU 50, as defined in the 3GPPT™ TS 25.322 specification. In general, there are two types of PDUs: a control PDU or a data PDU. Control PDUs are used by layer 2 to control data transmission and reception protocols. Data PDUs are used to transmit acknowledged mode data, which is then reassembled and presented to layer 3 as layer 2 SDUs. The example PDU 50 is a data PDU, and is divided into several fields, as defined by the layer 2 protocol. The first field 51 is a single bit indicating that the PDU 50 is either a data or a control PDU. As the data/control bit 51 is set (i.e., equal to 1), the PDU 50 is marked as an acknowledged mode data PDU. The second field 52 is a sequence number (SN) field, and is twelve bits long. Successive PDUs have successively higher sequence numbers, and in this way a receiver can properly reassembled PDUs to form SDUs. That is, if a PDU is transmitted with an SN equal to 536, the next PDU would be transmitted with an SN equal to 537, and so forth. A single polling bit 53 follows the SN field 52, and when set indicates that a receiver of the PDU 50 should respond with an acknowledgment status PDU, which is one kind of control PDU, and which will be introduced later. Bit 54 is reserved and is set to zero. The next bit 55a is an extension bit, and when set indicates the presence of a following length indicator (LI). An LI may be either 7 bits long or 15 bits long, and is used to indicate the ending position of an SDU within the PDU. If a single SDU completely fills the data region 58 of the PDU 50, then the bit 55a would be zero, thereby indicating that no LI is present. In the example PDU 50, however, there are two SDUs ending in the PDU 50: SDU157a and SDU257b. There must, therefore, be two LIs to indicate the respective ends of the SDU157a and the SDU257b. A PDU following the PDU 50 would hold the LI for SDU357c. The first LI, LI1, is in field 56a following the extension bit field 55a, and marks the end of the SDU157a. LI156a has an extension bit 55b that is set, indicating the presence of another LI, LI2 in field 56b. LI256b indicates the ending position of the SDU257b, and has an extension bit 55c that is cleared, signifying that there are no more LIs, and that the data region 58 is thus beginning.
In the following discussion, stations may be base stations, mobile units, personal data assistants, or other devices that use a three-layered wireless communications protocol. Each station has a receiving window that is delimited by two state variables: VR(R) and VR(MR). VR(R) marks the beginning of the receiving window of the station, and VR(MR) marks the end of the receiving window, exclusively. That is, the SN value held by VR(MR) is not included in the receiving window, whereas the SN values sequentially before VR(MR), and on or after VR(R), are within the receiving window. Each station expects to receive only PDUs that have SN values that land within the receiving window. Other PDUs are discarded. To better understand this, please refer to FIG. 4. FIG. 4 is a phase diagram 70 for a receiving window 73. In FIG. 4, the receiving window 73 has a VR(R)=3852 at position 71, and a VR(MR)=206 at position 72. At position 74, the SN values roll over to zero due to the finite bit-length of the SN field in PDUs. The maximum possible SN value is 4095 (i.e., 212−1). The receiving window 73 thus has a width of 450 PDUs. VR(MR) is always kept a fixed PDU SN value distance away from VR(R). That is, VR(MR)=VR(R)+the receiving window width (i.e., 450). As PDUs are received, the station advances VR(R), and thus advances the receiving window 73. VR(R) may not advance past any PDU that has not yet been properly received.
Please refer to FIG. 5. FIG. 5 is a phase diagram 80 for a transmitting window 83. In a manner analogous to the receiving window 73, each station also has a transmitting window 83 that is delimited by two state variables: VT(A) and VT(MS). VT(A) marks the beginning of the transmitting window 83, and VT(MS) marks the end of the transmitting window 83, exclusively. That is, the SN value held by VT(MS) is not included in the transmitting window 83, whereas the SN values sequentially before VT(MS), and on or after VT(A), are within the receiving window 83. VT(MS) is kept a fixed PDU SN value distance away from VT(A), i.e., VT(MS)=VT(A)+transmitting window width. For FIG. 5, VT(A)=3752 at position 81, and VT(MS)=106 at position 82. Again, roll over to zero occurs at position 84. The transmitting window 83 is thus also 450 PDUs wide. A station may only transmit PDUs that have SN values falling within the range of the transmitting window 83. Each transmitting station advances VT(A), and thus advances the transmitting window 83, upon reception of an acknowledgment status PDU from a receiving station. The acknowledgment status PDU contains the most recent value of VR(R) from the receiving station, and is sent periodically or upon receipt of a PDU with the polling bit 53 set. When an acknowledgment status PDU is received, the transmitting station sets its state variable VT(A) equal to the VR(R) value contained in the acknowledgment status PDU. In this manner, the transmitting window 83 of a transmitting station should ideally move forward in lock step with the receiving window 73 of a receiving station.
As the receiving window 73 and the transmitting window 83 advance with each other, PDUs stream from the first station are assembled into corresponding SDUs by the second station. These SDUs are then passed in order to layer 3. As noted previously, the communications protocol requires that SDUs be delivered to layer 3 fully whether the connection is in the in-sequence delivery mode or in the of out-of-sequence mode. However, the protocol does allow SDUs to be discarded. This may occur, for example, due to a timeout, in which the data in the SDU is no longer relevant. When a layer 2 SDU is discarded at the layer 2 level, i.e., by discarding the layer 2 PDUs that carry the layer 2 SDU, layer 2 must inform layer 3 of the SDUs that were discarded. To discard layer 2 SDUs, the first station sends layer 2 control PDUs to the second station indicating which SDUs are to be discarded. Upon reception of this control PDU, the second station adjusts its receiving window 73 accordingly, and informs its layer 3 of the SDUs that have been discarded. The second station then informs the first station that the discarding procedure has been performed by sending a layer 2 discarding control acknowledgment PDU. Upon receipt of the acknowledgment PDU from the second station, the first station layer 2 interface informs its layer 3 interface of the discarded SDUs. In this manner, the layer 3 interfaces of the first and second stations are both properly informed of discarded SDUs, and the discarded SDUs should be the same for both stations. That is, both the first station layer 3 and the second station layer 3 should agree upon the SDUs that were discarded, thus ensuring that applications and the layer 3 signaling messages in the two stations have proper data-synchronization with each other.
The control PDU sent by the first station to the second station for discarding SDUs is termed a Move Receiving Window (MRW) request PDU. Please refer to FIG. 6. FIG. 6 shows an MRW super-field 90 in an MRW request PDU 91. The MRW super-field 90 comprises a type field 92 of four bits that identifies the PDU 91 as an MRW request PDU, a length field 93 of four bits for indicating the number of subsequent SN_MRW entries 96, and an NLength field 95 of four bits. If the length field 93 holds a value of zero, then the MRW request PDU 91 will have only one subsequent SN_MRW entry 94, which contains an SN value that extends beyond the transmitting window of the first station. Each SN_MRW entry 94, is 12 bits wide and is used to indicate the end of a discarded SDU, containing the SN value for the PDU that holds the end of the discarded SDU. The last entry SN_MRWLength 94a, together with the NLength entry 95, informs the second station how the state variable VR(R) for its receiving window should be set. The NLength entry 95 indicates how many LIs and corresponding data in the SN_MRWLength PDU should be discarded. The second station updates the state variable VR(R), which marks the beginning of the receiving window, to the value in the SN_MRWLength field 94a if the original VR(R) has a value sequentially before the value in the SN_MRWLength field 94a. 
After processing the MRW request PDU 91, the second station sends back to the first station an acknowledgement PDU, which is called an MRW acknowledgment PDU. Please refer to FIG. 7, with reference to FIG. 6. FIG. 7 shows an MRW acknowledgment PDU 60. The MRW acknowledgment PDU 60 comprises three fields: a type field 62, an N field 65 and an SN_ACK field 64. The type field 62 is four bits wide and is set to a value that identifies the control PDU 60 as an MRW acknowledgment PDU 60. The N field 65 is also 4 bits wide and is set equal to the NLength field 95 of the original MRW request PDU 91 that is being acknowledged if the SN_ACK field 64 is equal to the SN_MRWLength field 94a of the original MRW request PDU 91 that is being acknowledged. Otherwise, the N field 65 is set equal to zero. The SN_ACK field 64 is 12 bits wide, and is set equal to the updated VR(R) value after the reception and execution of the MRW request PDU 91. Upon receipt of the MRW acknowledgment PDU 60, the first station can determine that the second station has processed the original MRW request PDU 91 and the original SDU discarding procedure is terminated. A new SDU discarding procedure can be started only after the previous SDU discarding procedure has been terminated.
To better understand the above, please refer to FIG. 8 and FIG. 9, with reference to FIG. 1. FIG. 8 is a diagram of a string of SDUs 100. FIG. 9 illustrates a sample MRW super-field 110 for discarding a portion of the SDUs 100 shown in FIG. 8. In FIG. 8, individual layer 2 PDUs that carry the layer 2 SDUs 100 are marked with dotted lines. SDU_11 ends in a PDU 101 having an SN value of 90. SDU_12 ends in a PDU 102 having an SN value of 95. SDU_13 and SDU_14 both end in a PDU 103 having an SN value of 96. Finally, SDU_15 begins in a PDU 104 with an SN value of 97. To discard SDU_11, SDU_12 and SDU_13, the first station 10 builds the MRW super-field 110 and sends the MRW super-field 110 to the second station 20 as an MRW request PDU 111. The type field 112 is set to an MRW type indicator. The length field 113 holds a value of three, indicating that three SN_MRW entries follow. SN_MRW1 entry 114 is set to 90, indicating the end position of SDU_11 that is to be discarded, corresponding to PDU 101. The second entry SN_MRW2 115 is set to 95, indicating that SDU_12, which is to be discarded, ends in PDU 102. Finally, the last entry SN_MRW3 116, together with N3 117 equal to 1, indicates that the first LI in PDU 103, and the data the LI references, are to be discarded. This corresponds, then, to throwing out SDU_13. SDU_14, on the other hand, is kept.
Please refer to FIG. 10 with reference to FIGS. 8, 9 and 1. FIG. 10 illustrates an MRW acknowledgment PDU 120 sent by the second station 20 to the first station 10 after processing the MRW request PDU 111. The MRW acknowledgment PDU 120 comprises a type field 121 that identifies the PDU 120 as an MRW acknowledgment PDU, an N field 127 that is set equal to the N3 field 117 in the original MRW request PDU 111, and an SN_ACK field 126 that is equal to the SN_MRW3 field 116 in the MRW request PDU 111. Upon receipt of the MRW acknowledgment PDU 120, by parsing the N field 127 and the SN_ACK field 126, the first station 10 can know that the second station 20 responded to the original MRW request PDU 111, and that the second station 20 has advanced its receiving window starting point VR(R) to 96, i.e., to the value indicated in the SN_ACK field 126. The first station 10 thus assumes that the second station 20 has discarded SDU_11, SDU_12 and SDU_13, and is waiting for layer 2 PDU 103 to begin processing of SDU_14 and the following layer 2 SDUs. The layer 2 interface 16 of the first station 10 thus informs the layer 3 interface 12 that SDU_11, SDU_12 and SDU_13 have been discarded. In FIG. 8, arrow 105 marks a hypothetical position of the receiving window state variable VR(R) for the second station 20. That is, prior to processing the MRW request PDU 111, the second station 20 was waiting for a layer 2 PDU 106 and the subsequent layer 2 PDU 101 from the first station 10 to complete layer 2 SDU_11. However, after processing the MRW request PDU 111, the second station 20 throws away all data that had been collected for SDU_11, and advances VR(R) forward (thus advancing the receiving window) to a position indicated by arrow 107, which corresponds to an SN value of 96. The second station 20 thus awaits reception of the PDU 103 and subsequent PDUs from the first station 10 to process SDU_14, SDU_15 and so on. As with the first station 10, the second station 20 layer 2 interface 26 informs the layer 3 interface 22 of the discarded SDU_11, SDU_12 and SDU_13. The first and second stations 10 and 20 thus both agree upon the SDUs discarded by the MRW request PDU 111 and subsequent MRW acknowledgment PDU 120.
In general, the receiving window of the second station 20 will advance beyond the transmitting window of the first station 10 since the second station 20 reports with an acknowledgement status PDU on a periodic base or after it receives a poll from the first station 10, which does not trigger a poll with every layer 2 PDU sent. Additionally, the first station 10 may occasionally fail to receive an acknowledgment status PDU from the second station 20 (due to interference, etc.), and thus will fail to update its transmitting window to reflect the new state of the second station 20 receiving window. The first station 10 may thus not be aware of how far advanced is the receiving window of the second station 20, and consequently request that the second station 20 discard a complete layer 2 SDU. For example, consider FIG. 11, with reference to FIGS. 1, 9 and 10. FIG. 11 is a diagram of the string of layer 2 SDUs 100 depicted in FIG. 8 with an advanced receiving window for the second station 20. The start of the receiving window, VR(R), is advanced slightly to the layer 2 PDU 102, as indicated by arrow 105a. That is, VR(R)=95 for the second station 20, and the second station 20 is waiting on the PDU 102 to complete layer 2 SDU_12. SDU_11, on the other hand, has already been completely received and passed up to the layer 3 interface 22 of the second station 20 as a layer 2 SDU. The first station 10, having failed to receive an acknowledgment status PDU from the second station 20, sends the MRW request PDU 111, perhaps due to an acknowledgment time-out. As before, the second station 20 will respond to the MRW request PDU 111 with the MRW acknowledgment PDU 120, and advance VR(R) to the position indicated by the arrow 107. As the second station 20 has already received SDU_11 and passed it up to the layer 3 interface 22, the layer 2 interface 26 will simply inform the layer 3 interface 22 that SDU_12 and SDU_13 have been discarded. The first station 10, however, upon receipt of the MRW acknowledgment PDU 120 from the second station 20, will still inform its layer 3 interface 12 that SDU_11, SDU_12 and SDU_13 have been discarded. Application 13 on the first station 10 thus mistakenly believes that application 23 on the second station 20 has not received the layer 2 SDU SDU_11.